package com.daji.search_and_sort;

import java.util.Arrays;
// 参考资料：https://blog.csdn.net/qq_40941722/article/details/94396010
public class QuickSort {

    public static void main(String[] args) {
        int []arr = {7,6,12,11,5,12,0,3,7,20};
        Quick_Sort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));

        // Quick_Sort2(arr,0, arr.length-1);
        // System.out.println(Arrays.toString(arr));
    }


    private static void Quick_Sort(int[] arr, int begin, int end){
        if(begin > end)
            return;
        int tmp = arr[begin];
        int i = begin;
        int j = end;
        while(i != j){
            while(arr[j] >= tmp && j > i)
                j--;
            while(arr[i] <= tmp && j > i)
                i++;
            if(j > i){  //swap(arr[i], arr[j])
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //下面两行其实作用就是：swap(arr[i],arr[begin])
        arr[begin] = arr[i];
        arr[i] = tmp;
        //i就是中间那个，已经被排序好的元素
        Quick_Sort(arr, begin, i-1);    //递归快排左边
        Quick_Sort(arr, i+1, end);      //递归快排右边
    }

    /**
     * 参考资料：https://blog.csdn.net/qq_40941722/article/details/94396010
     * 
     * WZR 2022年9月11日 21:55:20 重新手写快排（只看了原理，没看具体代码实现。纯手撕）
     * 这次重写失败了。失败原因是没有意识到隐含条件：
     * 首先哨兵j 开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j 先出动，这一点非常重要。哨兵j一步一步地向左挪动（即j = j − 1 j = j-1j=j−1），直到找到一个小于6的数停下来。
     * 接下来哨兵i 再一步一步向右挪动（即i = i + 1 i=i+1i=i+1），直到找到一个数大于6的数停下来。
     * 
     * 我忽视了哨兵i 和 哨兵j ，是只有一个停下了，另一个才可以出动。所以只能用双while循环了！
     * 我忽视了哨兵i 和 哨兵j ，是只有一个停下了，另一个才可以出动。所以只能用双while循环了！
     * 我忽视了哨兵i 和 哨兵j ，是只有一个停下了，另一个才可以出动。所以只能用双while循环了！
     * 我忽视了哨兵i 和 哨兵j ，是只有一个停下了，另一个才可以出动。所以只能用双while循环了！
     * 
     * 下面这一版代码作废。记住这个错误，别再犯了
     * 
     * @param arr
     * @param begin
     * @param end
     */
    private static void Quick_Sort2(int[] arr, int begin, int end){
        //非常重要的递归结束条件：（这里我忘了！）
        if(begin > end)
            return;

        int base = arr[begin];
        int i = begin;
        int j = end;
        // 左边都比base小，右边都比base大。如果发现一对，则立马交换
        while (true) {
            if (arr[i] <= base) { //言下之意：如果发现arr[i] > base, 那么就停止i的步进 
                i++;   
                if (i > end) {
                    i--;
                    break;
                }
            }

            if (i == j){
                //直到i 和 j 相遇，说明走完了，可以把初始的base换到相遇点
                //互换arr[begin] 和 arr[i]
                int temp = arr[begin];
                arr[begin] = arr[i];
                arr[i] = temp;
                //互换结束
                break;
            }

            if (arr[j] >= base) {
                j--;
                if (j < begin) {
                    j++;
                    break;
                }
            }

            if (i == j){
                //直到i 和 j 相遇，说明走完了，可以把初始的base换到相遇点
                //互换arr[begin] 和 arr[i]
                int temp = arr[begin];
                arr[begin] = arr[i];
                arr[i] = temp;
                //互换结束
                break;
            }

            if (arr[i] > base && arr[j] < base) { //找到了，该互换了
                //互换arr[i] 和 arr[j]   //swap(arr[i], arr[j])
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                //互换结束
            }
            //互换结束后，i和j可以继续搜索并往下走，while循环继续执行
            //直到i 和 j 相遇，说明走完了，可以把初始的base换到相遇点
        }        

        //结束此while循环后，说明i和j相等，此时i和j所在的元素处：左边的全部比它小，右边的全部比它大
        //递归调用这个Quick_Sort，问题即可解决
        Quick_Sort2(arr, begin, i-1);
        Quick_Sort2(arr, i+1, end);
    }


}
